package club.xiaojiawei.dp;

import java.util.Arrays;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 6/9/22 12:07 AM
 * @question 72. 编辑距离
 * @description 给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数。
 * 你可以对一个单词进行如下三种操作：
 * 插入一个字符
 * 删除一个字符
 * 替换一个字符
 */
public class MinDistance72 {

    public static void main(String[] args) {
        MinDistance72 test = new MinDistance72();
        int result = test.minDistance("intention", "execution");
        System.out.println(result);
    }

    /**
     * 官方-dp
     * 从头部到尾部
     * 时间复杂度 ：O(mn)
     * 空间复杂度 ：O(mn)
     * @param word1
     * @param word2
     * @return
     */
    public int minDistance(String word1, String word2) {
        int n = word1.length();
        int m = word2.length();
        // 有一个字符串为空串
        if (n * m == 0) {
            return n + m;
        }
        // DP 数组D[i][j] = k 表示word1从头部到下标i处的字符串变成和word2从头部到下标j处的字符串相同需要的最小操作步数为k
        int[][] D = new int[n + 1][m + 1];
        // 边界状态初始化
        for (int i = 0; i < n + 1; i++) {
            D[i][0] = i;
        }
        for (int j = 0; j < m + 1; j++) {
            D[0][j] = j;
        }
        // 计算所有 DP 值
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                int left = D[i - 1][j] + 1;
                int down = D[i][j - 1] + 1;
                int left_down = D[i - 1][j - 1];
                if (word1.charAt(i - 1) != word2.charAt(j - 1)) {
                    left_down += 1;
                }
                D[i][j] = Math.min(left, Math.min(down, left_down));
            }
        }
        return D[n][m];
    }

    /**
     * 民间-递归回溯（记忆搜索法）
     * 先从尾部递归到头部，然后再从头部回溯到尾部
     * @param word1
     * @param word2
     * @return
     */
    public int minDistance2(String word1, String word2){
        int m = word1.length();
        int n = word2.length();
        memo = new int[m][n];
        for(int[] v : memo){
            Arrays.fill(v,-1);
        }
        return minD(word1, m-1, word2, n-1);

    }

    /**
     * memo[i][j] = k 表示word1从头部到下标i处的字符串变成和word2从头部到下标j处的字符串相同需要的最小操作步数为k
     */
    int[][] memo;

    public int minD(String word1, int i, String word2, int j){
        if(i == -1){
            return j + 1;
        }
        if(j == -1){
            return i + 1;
        }
        if(memo[i][j] != -1){
            return memo[i][j];
        }
        if(word1.charAt(i) == word2.charAt(j)){
            memo[i][j] =  minD(word1, i-1, word2, j-1);
        }else{
            memo[i][j] =  getMin(minD(word1, i, word2, j - 1), minD(word1, i - 1, word2, j), minD(word1, i - 1, word2, j - 1)) + 1;
        }
        return memo[i][j];
    }

    public int getMin(int a, int b, int c){
        int min = Math.min(a, b);
        min = Math.min(min, c);
        return min;
    }
}
